package lc_1847_最近的房间;

import java.util.Arrays;
import java.util.TreeSet;

public class Solution {
	public int[] closestRoom(int[][] rooms, int[][] queries) {
		Arrays.sort(rooms, (a, b) -> b[1] - a[1]);
		int len = queries.length;
		Integer[] ids = new Integer[len];
		for (int i = 0; i < len; i++) {
			ids[i] = i;
		}
		int[] ans = new int[len];
		Arrays.fill(ans, -1);
		Arrays.sort(ids, (a, b) -> queries[b][1] - queries[a][1]);
		TreeSet<Integer> ts = new TreeSet<>();
		for (int i = 0, j = 0; i < len; i++) {
			int id = ids[i];
			int queryid = queries[id][0], querysize = queries[id][1];
			while (j < rooms.length && rooms[j][1] >= querysize) {
				ts.add(rooms[j][0]);
				j++;
			}
			Integer ceil = ts.ceiling(queryid);
			Integer floor = ts.floor(queryid);
			if (floor != null) {
				ans[id] = floor;
			}
			if (ceil != null && (ans[id] == -1 || ceil - queryid < queryid - floor)) {
				ans[id] = ceil;
			}

		}
		return ans;
	}

	public static void main(String[] args) {
		TreeSet<Integer> ts = new TreeSet<>();

		System.out.println(ts.ceiling(300));
		System.out.println(ts.ceiling(150));
	}
}
